1. Field of the Invention
The present invention relates to digital circuits used to control the flow of binary data within a local area network. In particular, the present invention relates to a network interface controller which manipulates and controls the flow of binary data between a digital system and a local area network shared by that digital system with other digital systems.
2. Description of the Related Art
As digital data communications systems have become more sophisticated, users of such systems have been able to more fully take advantage of this sophistication by interconnecting several digital systems via a network (e.g., a local area network or "LAN"). A network promotes synergy among the systems by allowing them to communicate with each other and share applications and data. However, with several systems trying to communicate with each other, some form of communications protocol must be observed lest communication pandemonium result. By establishing an appropriate communications protocol, the sharing of applications and data among the systems sharing the network can be accomplished in an efficient and orderly manner. One example of such a communications protocol which is quite common is called "Ethernet."
As is known in the art, Ethernet is a commonly used term for a communications protocol standard. It is also known as "Carrier Sense with Multiple Access and Collision Detect" ("CSMA/CD") and is defined by the Institute of Electrical and Electronics Engineers' (I.E.E.E.) standard 802.3.
FIG. 1 is a simplified, functional block diagram of a typical integrated Ethernet interface 10 with an ordinary media access controller ("MAC") 11 and network and system interfaces. The primary functional elements of this interface 10 are: a MAC 11; a media attachment unit ("MAU") 13; an attachment unit interface ("AUl") 12; an encoder/decoder 14; a deserializer and receiver interface 16; a serializer and transmitter interface 18; a receiver first-in, first-out ("FIFO") register 20; a transmitter FIFO 22; and a system interface 24.
The AUI 12 provides the appropriate logic and circuitry needed to interconnect with and communicate over the network medium via the MAU 13. The encoder/decoder 14 provides the data encoding and decoding functions needed for communicating over the Ethernet network. During reception, the encoder/decoder 14 decodes Manchester encoded data received from the network medium via the MAU 13 into non-return-to-zero ("NRZ") formatted data for utilization by the user system (not shown). The encoder/decoder 14 also recovers a received data clock for the NRZ data from the Manchester encoded signal. The received NRZ data and clock are sent to the deserializer and receiver interface 16.
During transmission, the encoder/decoder 14 combines the NRZ data and data clock signals into Manchester encoded data which is sent to the AUI 12 for transmission onto the network medium. The encoder/decoder 14 further provides a "carrier sense" signal which indicates the presence of a data signal on the network medium and a "collision sense" signal which indicates the presence of a transmission collision (two user systems attempting to transmit simultaneously) within the Ethernet network.
The deserializer and receiver interface 16 monitors the incoming serial NRZ data 26 provided by the encoder/decoder 14 during reception. After detecting a start-of-frame delimiter ("SFD") pattern within the Ethernet signal, the deserializer and receiver interface 16 then frames the incoming data bits 26 into eight-bit wide bytes and transfers this byte-wide data 28 to the receiver FIFO 20. The data stored in the receiver FIFO 20 is then transferred via the system interface 24 to the user system (not shown).
During data transmission, the transmitter FIFO 22 stores data received from the user system via the system interface 24. This stored data is transferred in eight-bit wide bytes to the serializer and transmitter interface 18. The serializer and transmitter interface 18 converts this byte-wide data 30 to a serial NRZ data stream and clock 32 for transfer to the encoder/decoder 14.
Further communication and sharing of instructions and data is accomplished among the primary elements 16, 18, 20, 22, 24 of the interface 10 by way of a parallel data bus 34.
FIG. 2 is a functional block diagram illustrating in more detail the deserializer and receiver interface 16. Its primary elements, a deserializer 36, a cyclic redundancy check ("CRC") checker 38 and a receiver state machine 40, interconnect with the encoder/decoder 14, receiver FIFO 20 and system interface 24. As described above, the deserializer 36 accepts the incoming serial NRZ data and recovered received data clock 26 from the encoder/decoder 14 and converts it to eight-bit wide bytes of data 28 for transfer to the receiver FIFO 20. The CRC checker 38 calculates the four-byte frame check sequence ("FCS") field from the incoming data stream 26 and compares it with the last four bytes of the received packet of data 26 to verify data integrity. The receiver state machine 40 contains the command, control and status registers that govern the operations of the deserializer 36 and CRC checker 38. The receiver state machine 40 further generates control signals for instructing the receiver FIFO 20 to store its incoming data 28 and processes CRC error signals received from the CRC checker 38.
In order to take further advantage of the sophistication and versatility of today's digital systems, a network "bridge" may be constructed whereby networks of interconnected digital systems are themselves interconnected. In other words, a network having multiple digital systems interconnected therein may be coupled so as to interconnect with another network also having multiple digital systems interconnected therein.
FIG. 3 illustrates a simplified, functional block diagram of a network bridge 50. FIG. 3 illustrates the situation where three networks are bridged. However, conceivably, virtually any number of networks may be bridged together. The bridging of the multiple networks is accomplished by a system bus 52. It is over this system bus 52 that the three networks 54, 56, 58 communicate via their respective MACs 60, 62, 64. The bridging operation is controlled by the system CPU 66 and the information to be bridged from one network to another is buffered by the system memory 68.
The operation and/or configuration of the typical MAC present several problems. One problem involves the handling of received data that has been decoded and deserialized. Current MACs process all information appearing on the network for storage within the user system (not shown). It is then up to the user system to devote time and software for determining whether to retain and use that processed information or to discard it. One way of making this determination is to examine the destination address field within the incoming Ethernet data packet to determine if the data packet is intended for that particular user's system. Current MACs only a single physical address and provide no support for restricted group usage or multiple service access points. They also use a non-deterministic "hashing" scheme to examine the incoming address field for filtering out undesired data packets.
A hashing scheme involves the use of a complex mathematical algorithm to distinguish among different address values. For example, one hashing scheme provides for performing a calculation on a 48-bit address field to reduce it to a 32-bit field. The first (i.e., the most significant) six bits are then used as an address to access a 64-bit lookup table wherein a logical one or zero has been stored to indicate whether to accept or reject, respectively, the data packet containing the original 48-bit address field.
Although the hashing scheme may distinguish between specific, individual addresses, it does not guarantee generating different "hash" values for different addresses. Therefore, the hashing filter may sometimes incorrectly recognize addresses, thereby rendering it useless for user systems which demand deterministic address recognition. Such shortcomings in the address filtering capability of current MACs have required system designers to use complex external circuitry and software filters to provide the necessary filtering (e.g., routers and bridges, as discussed more fully below).
Thus, it would be desirable to have an address filtering scheme which does not require the use of the complex mathematical algorithms used in a hashing scheme. It would be further desirable to have an address filtering scheme which is deterministic and therefore capable of recognizing each and every potential individual address. It would be still further desirable to have an address filtering scheme which not only supports single physical addresses but also supports restricted group usage and multiple service access points.
A second problem involves the network bridge 50 discussed above for FIG. 3. This problem is similar to that just discussed, in that it involves address filtering. The purpose of the bridge 50 is to monitor the data packets generated within one network, via the associated MAC, and determine whether that data packet is intended to be used within that network or within another network. If the data packet is intended for use within another network, the bridge 50 must capture and retain that data packet and route, or "bridge," that data packet to the appropriate network.
For example, in FIG. 3, a data packet generated in network A is captured and retained by its associated MAC A and placed on the system bus 52 for temporary storage within the system memory 68. The bridge 50 then, through appropriate programming of the system CPU 66, determines whether that data packet stored in the system memory 68 was intended for use within the original network A, or was intended to be bridged to networks B and/or C (via their associated MACs B, C). If intended for network B and/or C, the data packet is read out from the system memory 68 over the system bus 52 and transferred to the MAC(s) of the appropriate network(s). However, if the data packet was intended for use only within network A, then the use of the system bus 52 and system memory 68 to transfer and store that data packet was not only inefficient usage of the bus 52 and memory 68, but was also counterproductive. This counterproductivity arises from the unavailability of the system bus 52 and system memory 68 for the bridging of other data packets which are intended for transfer to and use within other networks served by the bridge 50.
Thus, it would be desirable to have some form of MAC support for address filtering which would make an early determination as to whether a data packet generated by one network needs to be bridged to other networks. Such an early determination would minimize usage of the system bus 52 and system memory 68 to buffer data packets, or portions thereof, which are subsequently determined not to be bridged, and therefore not to be buffered. This would make the system bus 52 and system memory 68 available more often, thereby increasing the effective throughput of the bus 52 and bridge 50. It would be further desirable that such address filtering be versatile enough to support multiple network bridging algorithms (e.g., spanning tree and source routing).
A still further problem with current MACs involves the CRC checker 38. FIGS. 4 and 5 illustrate in functional block diagram form a typical CRC checker 38. The primary functional elements include multiple exclusive-OR gates 70 and single-bit shift register elements 72, plus a CRC comparator 4, which in turn, is made up of several AND gates 76 and two inverters 78 (See FIG. 5).
The incoming serial NRZ data 26 passes through the exclusive-OR gates 70 and shift register elements 72 as shown in FIG. 4. This combinational logic 70, 72 produces a binary result 80 which is a parallel binary signal made up of the 32 output bits from the shift register elements 72. This 32-bit wide signal 80 is compared within the CRC comparator 74 to see whether any errors have been introduced into the data packet prior to its arrival at the CRC checker 38. The CRC comparator 74 illustrated in FIG. 5 is designed to check for the CRC bit pattern: 1100 0111 0000 0100 1101 1101 0111 1011.
Using a CRC scheme to detect errors in data transmission is known in the art. Discussions of the algorithms involved and examples thereof may be found in: "The Great CRC Mystery", by Terry Ritter, published in Dr. Dobb's Journal, February 1986; and "Calculating CRCs By Bits And Bytes", by Greg Morse, published in BYTE magazine, September 1986. A discussion and example specifically involving Ethernet may be found in "The Ethernet, A Local Area Network, Datalink Layer and Physical Layer Specifications", Sep. 30, 1980, published jointly by Digital Equipment Corporation, Intel Corporation and Xerox Corporation.
The specific problem related to the CRC checker 38 is that of testability. As with any integrated circuit, following fabrication thereof the circuitry constituting the CRC checker 38 must undergo functional electrical testing. In order to fully test all circuit interconnections, all bit permutations of the 32-bit input signals 26 must be clocked through the exclusive-OR gates 70 and shift register elements 72. By doing this, it can be determined conclusively whether only one bit pattern produces a condition of no CRC error. Therefore, a total of 2.sup.32 different 32-bit patterns must be serially shifted through these logic elements 70, 72 to conclusively determine the integrity of the circuit connections within the CRC checker 38. Inputting such a large number of such long bit patterns for testing requires a relatively large amount of time, even with automated test equipment.
Furthermore, due to the effects of the logic elements 70, 72 (see articles referenced above), the 2.sup.= unique 32-bit patterns must be calculated, one for each of the 2.sup.32 different 32-bit tested, so that all bit permutations will be included in the test. Such a large number of bit permutation calculations is burdensome and time consuming, even with the aid of automated test equipment. Thus, it would be desirable to have a circuit for a CRC checker 38 which would provide the requisite CRC checking function, but which would not require the extensive and burdensome bit permutation calculations and the prolonged test time associated therewith.
A still further problem involves the transmitter FIFO 22 and its buffering of data intended for transmission into the network. The system interface 24, when fetching data fragments from the user system (not shown), fetches four bytes (i.e., a double word) at a time when a 32-bit wide data bus is used (or two bytes (single word) when a 16-bit wide data bus is used). Since not all data fragments necessarily contain a number of bytes which is evenly divisible by four (or two), this necessarily means that some of the bytes fetched by the system interface 24 will be invalid. However, prior to transmission, all such invalid data must be eliminated. In other words, only valid data bytes are to be transmitted into the network, with no invalid data bytes intertwined therewith.
Currently, to ensure that only valid data is buffered by the transmitter FIFO 22 for transmission into the network, the MAC must be programmed to examine the data that it fetches from the user system (not shown) and filter out or otherwise discard any invalid data bytes. Depending upon how misaligned the desired data bytes are within the user system, realignment of the byte boundaries for valid data bytes can consume a great deal of processing time and require complex programming. Furthermore, this programming requires sufficient program memory within the MAC to support this realignment process, memory which could otherwise be used for more productive purposes.
Therefore, it would be desirable to have a simplified method and/or circuit which would either filter out invalid data bytes or eliminate the need for such filtering. It would be further desirable to provide for such elimination of invalid data bytes without requiring overhead software to support this process. It would be still further desirable to provide for this elimination of invalid data bytes within the transmitter FIFO 22, thereby freeing up the system interface 24 and/or user system for more productive operations.